{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Integer arithmetic\n",
    "\n",
    "Many quantum algorithms need to evaluate classical functions on a superposition of inputs. An example is Shor's algorithm, which requires the mapping $|x\\rangle|0\\rangle\\mapsto|x\\rangle|a^x\\text{ mod }N\\rangle$ to be implemented as a quantum operation.\n",
    "\n",
    "To keep users from having to implement such functions from scratch, the Q# standard library contains arithmetic functionality such as integer adders."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's write a wrapper for one of these adders, that of [Takahashi *et al.*](https://arxiv.org/abs/0910.2530). This will allow us to quickly exchange it for a different implementation if need be."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "name": "add-operation",
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "application/json": "[\"Add\"]",
      "text/html": [
       "<ul><li>Add</li></ul>"
      ],
      "text/plain": [
       "Add"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "open Microsoft.Quantum.Arithmetic;\n",
    "\n",
    "operation Add(qint1 : LittleEndian, qint2 : LittleEndian, carry : Qubit) : Unit {\n",
    "    Message(\"[Using the adder by Takahashi et al. (arXiv:0910.2530)]\");\n",
    "    RippleCarryAdderTTK(qint1, qint2, carry);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Running the adder\n",
    "\n",
    "We can now use this wrapper in our code as a subroutine. As an example, let's write an operation that initializes two quantum integers to classical values (e.g., 4 and 5) before calling our `Add` operation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/json": "[\"TestAddition\"]",
      "text/html": [
       "<ul><li>TestAddition</li></ul>"
      ],
      "text/plain": [
       "TestAddition"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "open Microsoft.Quantum.Arithmetic;\n",
    "open Microsoft.Quantum.Measurement;\n",
    "open Microsoft.Quantum.Diagnostics;\n",
    "\n",
    "operation TestAddition() : Int {\n",
    "    let firstNumber = 4;\n",
    "    let secondNumber = 5;\n",
    "    let numBits = 3;\n",
    "\n",
    "    mutable result = 0;\n",
    "    Message($\"Calculating {firstNumber} + {secondNumber}...\");\n",
    "    using ((register1, register2, carry) = (Qubit[numBits], Qubit[numBits], Qubit())) {\n",
    "        let qint1 = LittleEndian(register1);\n",
    "        let qint2 = LittleEndian(register2);\n",
    "        \n",
    "        // initialize the two quantum integers:\n",
    "        ApplyXorInPlace(firstNumber, qint1);\n",
    "        ApplyXorInPlace(secondNumber, qint2);\n",
    "        \n",
    "        // perform addition\n",
    "        Add(qint1, qint2, carry);\n",
    "        \n",
    "        // show the resulting state of qint1.\n",
    "        DumpRegister((), qint2! + [carry]);\n",
    "        \n",
    "        // and measure the result\n",
    "        let mCarry = (MResetZ(carry) == One) ? 1 | 0;\n",
    "        set result = 2^numBits * mCarry + MeasureInteger(qint2);\n",
    "        ResetAll(register1 + register2);\n",
    "    }\n",
    "\n",
    "    // Return the measured result\n",
    "    return result;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now test our adder using the simulator:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/json": "\"true\"",
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%config dump.truncateSmallAmplitudes = true"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Calculating 4 + 5...\n",
      "[Using the adder by Takahashi et al. (arXiv:0910.2530)]\n"
     ]
    },
    {
     "data": {
      "application/json": "{\"QubitIds\":[3,4,5,6],\"NQubits\":4,\"Amplitudes\":[{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":1.0,\"Imaginary\":0.0,\"Magnitude\":1.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0}]}",
      "text/html": [
       "\r\n",
       "                    <table style=\"table-layout: fixed; width: 100%\">\r\n",
       "                        <thead>\r\n",
       "                            \r\n",
       "                        <tr>\r\n",
       "                            <th>Qubit IDs</th>\r\n",
       "                            <td span=\"3\">3, 4, 5, 6</td>\r\n",
       "                        </tr>\r\n",
       "                    \r\n",
       "                            <tr>\r\n",
       "                                <th style=\"width: 20ch)\">Basis state (little endian)</th>\r\n",
       "                                <th style=\"width: 20ch\">Amplitude</th>\r\n",
       "                                <th style=\"width: calc(100% - 26ch - 20ch)\">Meas. Pr.</th>\r\n",
       "                                <th style=\"width: 6ch\">Phase</th>\r\n",
       "                            </tr>\r\n",
       "                        </thead>\r\n",
       "\r\n",
       "                        <tbody>\r\n",
       "                            \r\n",
       "                            <tr>\r\n",
       "                                <td>$\\left|9\\right\\rangle$</td>\r\n",
       "                                <td>$1.0000 + 0.0000 i$</td>\r\n",
       "                                <td>\r\n",
       "                                    <progress\r\n",
       "                                        max=\"100\"\r\n",
       "                                        value=\"100\"\r\n",
       "                                        style=\"width: 100%;\"\r\n",
       "                                    >\r\n",
       "                                </td>\r\n",
       "                                \r\n",
       "                                <td style=\"transform: rotate(0deg);\r\n",
       "                   text-align: center;\">\r\n",
       "                                 ↑\r\n",
       "                                </td>\r\n",
       "                            \r\n",
       "                            </tr>\r\n",
       "                        \r\n",
       "                        </tbody>\r\n",
       "                    </table>\r\n",
       "                "
      ],
      "text/plain": [
       "|9⟩\t1 + 0𝑖"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/json": "9",
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%simulate TestAddition "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exchanging implementations\n",
    "Furthermore, we can quickly change the underlying adder implementation, e.g., to that of [Cuccaro *et al.*](https://arxiv.org/abs/quant-ph/0410184):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/json": "[\"Add\"]",
      "text/html": [
       "<ul><li>Add</li></ul>"
      ],
      "text/plain": [
       "Add"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "open Microsoft.Quantum.Arithmetic;\n",
    "\n",
    "operation Add(qint1 : LittleEndian, qint2 : LittleEndian, carry : Qubit) : Unit {\n",
    "    Message(\"[Using the adder by Cuccaro et al. (arXiv:0410184v1)]\");\n",
    "    RippleCarryAdderCDKM(qint1, qint2, carry);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's run our `TestAddition` operation again on the simulator:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Calculating 4 + 5...\n",
      "[Using the adder by Cuccaro et al. (arXiv:0410184v1)]\n"
     ]
    },
    {
     "data": {
      "application/json": "{\"QubitIds\":[3,4,5,6],\"NQubits\":4,\"Amplitudes\":[{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":1.0,\"Imaginary\":0.0,\"Magnitude\":1.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0},{\"Real\":0.0,\"Imaginary\":0.0,\"Magnitude\":0.0,\"Phase\":0.0}]}",
      "text/html": [
       "\r\n",
       "                    <table style=\"table-layout: fixed; width: 100%\">\r\n",
       "                        <thead>\r\n",
       "                            \r\n",
       "                        <tr>\r\n",
       "                            <th>Qubit IDs</th>\r\n",
       "                            <td span=\"3\">3, 4, 5, 6</td>\r\n",
       "                        </tr>\r\n",
       "                    \r\n",
       "                            <tr>\r\n",
       "                                <th style=\"width: 20ch)\">Basis state (little endian)</th>\r\n",
       "                                <th style=\"width: 20ch\">Amplitude</th>\r\n",
       "                                <th style=\"width: calc(100% - 26ch - 20ch)\">Meas. Pr.</th>\r\n",
       "                                <th style=\"width: 6ch\">Phase</th>\r\n",
       "                            </tr>\r\n",
       "                        </thead>\r\n",
       "\r\n",
       "                        <tbody>\r\n",
       "                            \r\n",
       "                            <tr>\r\n",
       "                                <td>$\\left|9\\right\\rangle$</td>\r\n",
       "                                <td>$1.0000 + 0.0000 i$</td>\r\n",
       "                                <td>\r\n",
       "                                    <progress\r\n",
       "                                        max=\"100\"\r\n",
       "                                        value=\"100\"\r\n",
       "                                        style=\"width: 100%;\"\r\n",
       "                                    >\r\n",
       "                                </td>\r\n",
       "                                <td style=\"transform: rotate(0deg);\r\n",
       "                   text-align: center;\">\r\n",
       "                                    ↑\r\n",
       "                                </td>\r\n",
       "                            </tr>\r\n",
       "                        \r\n",
       "                        </tbody>\r\n",
       "                    </table>\r\n",
       "                "
      ],
      "text/plain": [
       "|9⟩\t1 + 0𝑖"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/json": "9",
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%simulate TestAddition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Version information\n",
    "This notebook was last executed with:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/json": "{\"rows\":[{\"@type\":\"@tuple\",\"Item1\":\"iqsharp\",\"Item2\":\"0.11.2004.2825\"},{\"@type\":\"@tuple\",\"Item1\":\"Jupyter Core\",\"Item2\":\"1.3.52077.0\"},{\"@type\":\"@tuple\",\"Item1\":\".NET Runtime\",\"Item2\":\".NETCoreApp,Version=v3.1\"}]}",
      "text/html": [
       "<table><thead><tr><th>Component</th><th>Version</th></tr></thead><tbody><tr><td>iqsharp</td><td>0.11.2004.2825</td></tr><tr><td>Jupyter Core</td><td>1.3.52077.0</td></tr><tr><td>.NET Runtime</td><td>.NETCoreApp,Version=v3.1</td></tr></tbody></table>"
      ],
      "text/plain": [
       "Component    Version\r\n",
       "------------ ------------------------\r\n",
       "iqsharp      0.11.2004.2825\r\n",
       "Jupyter Core 1.3.52077.0\r\n",
       ".NET Runtime .NETCoreApp,Version=v3.1\r\n"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%version"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
